package sort.impl;

import sort.BaseSort;

public class QuickSort implements BaseSort {
    @Override
    public void safeSort(Comparable[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private void sort(Comparable[] arr, int left, int right){
        if(left >= right){
            return;
        }else{
            int pivot = partition(arr, left, right);
            sort(arr, left, pivot - 1);
            sort(arr, pivot + 1, left);
        }
    }

    private int partition(Comparable[] arr, int left, int right){
        int i = left, j = right;
        Comparable temp = arr[i];
        while (i < j){
            while (i < j && arr[j].compareTo(temp) >= 0){
                j--;
            }
            arr[i] = arr[j];
            while(i < j && arr[i].compareTo(temp) <= 0){
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;
        return i;
    }

}
